﻿/*
 * 二叉树的遍历和结构体定义
 */

//二叉树的存储方式：顺序存储和链式存储

/*
 * 二叉树的顺序存储：
 * 1. 适用于完全二叉树和满二叉树；
 * 2. 第i号结点存储在一维数组下标为i-1的分两种。
 * 3. 最坏情况下，一个高度为h且只有h个结点的单支树需要占据近2^h-1个存储单元
 * 4. 建议从数组下标为1开始存储树中的结点
 */
#include <cstdio>

#define MaxTreeSize 10
typedef char TElemType;
TElemType Nil = '#';   // 用"#"表示空

typedef TElemType SqBiTree[MaxTreeSize];  // 0号单元存储根结点

/*
 * 01. 已知一棵二叉树按顺序存储结构进行存储，设计一个算法，求编号分为为i和j的两个结点的最近的公共祖先结点的值。
 * 分析：在顺序存储中，第i号结点存储在第i号单元，存储在第i号结点的父结点的编号和存储单元是[i/2]。
 *      要找到第i号和第j号结点的公共祖先，分为三种情况。
 *      1、若i<j，说明结点j所在的层次大于或等于i所在的层次。结点j的父结点为j/2，在比较父结点和i的层次；
 *      2、若i>j，说明结点i所在的层次大于或等于j所在的层次。结点i的父结点为i/2，再比较父结点和j的层次；
 *      3、若i=j，说明找到了公共祖先。
 *      所以只要不断递归上述操作，直到第三种情况发生即可。
 */
TElemType Common_Ancestor(SqBiTree T, int i, int j){
    if(T[i]!='#'&&T[j]!='#'){
        while(i!=j){
            if(i<j)
                j=j/2;
            else
                i=i/2;
        }
        return T[i];
    }
}

int main(){
    SqBiTree T;
    Common_Ancestor(T, 2, 5);
    return 0;
}